package string.滑动窗口;

import java.util.Arrays;

/**
 * @Author kaho
 * @create 2020/11/30
 */
public class _209_长度最小的子数组 {


    /**
     * 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
     * <p>
     *  
     * <p>
     * 示例：
     * <p>
     * 输入：s = 7, nums = [2,3,1,2,4,3]
     * 输出：2
     * 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param s
     * @param nums
     * @return
     */
    public static int minSubArrayLen(int s, int[] nums) {
        int slow = 0, fast = 0, sum = 0, min = Integer.MAX_VALUE;
        while (fast < nums.length) {
            sum += nums[fast++];
            while (sum>=s) {
                min = Math.min(min, fast-slow);
                sum-=nums[slow++];
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }

    public static void main(String[] args) {
        int[] arr = {2,3,1,2,4,3};
        int i = minSubArrayLen1(17, arr);
    }


    /**
     * 我们申请一个临时数组 sums，其中 sums[i] 表示的是原数组 nums 前 i 个元素的和，
     * 题中说了 “给定一个含有 n 个 正整数 的数组”，既然是正整数，那么相加的和会越来越大，
     * 也就是sums数组中的元素是递增的。我们只需要找到 sums[k]-sums[j]>=s，那么 k-j 就是满足的连续子数组，
     * 但不一定是最小的，所以我们要继续找，直到找到最小的为止。怎么找呢，我们可以使用两个 for 循环来枚举，
     * 但这又和第一种暴力求解一样了，所以我们可以换种思路，
     * 求 sums[k]-sums[j]>=s 我们可以求 sums[j]+s<=sums[k]，那这样就好办了，
     * 因为数组sums中的元素是递增的，也就是排序的，我们只需要求出 sum[j]+s 的值，
     * 然后使用二分法查找即可找到这个 k。
     *
     * 作者：sdwwld
     * 链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/javade-jie-fa-ji-bai-liao-9985de-yong-hu-by-sdwwld/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param s
     * @param nums
     * @return
     */
    public static int minSubArrayLen1(int s, int[] nums) {
        int length = nums.length;
        int min = Integer.MAX_VALUE;
        int[] sums = new int[length + 1];
        for (int i = 1; i <= length; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 0; i <= length; i++) {
            int target = s + sums[i];
            int index = Arrays.binarySearch(sums, target);
            if (index < 0) {
                index = ~index;
            }
            if (index <= length) {
                min = Math.min(min, index - i);
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }

}
